package com.zjsru.plan2024.normal;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * 983. 最低票价
 * @Author: cookLee
 * @Date: 2024-10-07
 */
public class MincostTickets {

    /**
     * 主
     * \
     * 输入：days = [1,4,6,7,8,20], costs = [2,7,15]
     * 输出：11
     * 解释：
     * 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     * 在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
     * 在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
     * 在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
     * 你总共花了 $11，并完成了你计划的每一天旅行。
     * \
     * 输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
     * 输出：17
     * 解释：
     * 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     * 在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
     * 在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
     * 你总共花了 $17，并完成了你计划的每一天旅行。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MincostTickets mincostTickets = new MincostTickets();
        int[] days = new int[]{1,4,6,7,8,20};
        int[] costs = new int[]{2,7,15};
        System.out.println(mincostTickets.mincostTickets(days, costs));

    }

    /**
     * 记录到每天位置最适合的花费数，366表示一年的最大天数不超过此数
     */
    Integer[] memo;

    /**
     * 旅行天数
     */
    Set<Integer> travelDays = new HashSet<>();

    /**
     * 费用
     */
    int[] costs;

    /**
     * 花费门票
     *
     * @param days  天数
     * @param costs 费用
     * @return int
     */
    public int mincostTickets(int[] days, int[] costs) {
        this.costs = costs;
        this.memo = new Integer[366];
        for (int day : days) {
            this.travelDays.add(day);
        }
        return this.helper(1);
    }

    /**
     * 计算票价帮手类
     *
     * @param i 开始天数
     * @return int
     */
    private int helper(int i) {
        //超出天数
        if (i >= 366) {
            return 0;
        }
        if (this.memo[i] != null) {
            return this.memo[i];
        }
        if (this.travelDays.contains(i)) {
            this.memo[i] = Math.min(Math.min(this.helper(i + 1) + this.costs[0], this.helper(i + 7) + this.costs[1]), this.helper(i + 30) + this.costs[2]);
        } else {
            this.memo[i] = this.helper(i + 1);
        }
        return memo[i];
    }
}
